package com.tree.stack;

import com.alibaba.fastjson.JSON;

import java.util.Scanner;
import java.util.Stack;

/**
 * package com.tree.stack
 * description:
 * 题目：
 *  实现一个特殊的栈，在实现栈的基本功能上，再实现返回栈中最小的元素
 * 要求
 *  1. pop、push、getMin操作的时间复杂度O(1)
 *  2. 可以使用现成栈的结构
 * 思路：
 *  在设计上我们使用2个栈，一个栈保存当前元素，其功能和普通栈没有区别，stackData；
 *  另一个用户保存每一步的最小值，stackMin；
 *  下面用2种方法实现
 *
 *
 * @author tree
 * @date 2019-10-10 10:59
 */
public class MinStackData {

    private static Stack<Integer> stackData = new Stack<Integer>();
    private static Stack<Integer> stackMin = new Stack<Integer>();


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String str = input.nextLine();
        System.out.println("请输入：");
        while (str != null && !"".equals(str)){
            System.out.println(str);
            push1(Integer.parseInt(str));
            str = input.nextLine();
        }
        System.out.println("stackData="+ JSON.toJSONString(stackData));
        System.out.println("stackMin="+ JSON.toJSONString(stackMin));
        System.out.println("最小值"+getMin());

        /**
         * 输入4 6 3 1 5
         * stackData=[4,6,3,1,5]
         * stackmin=[4,3,1]
         * 最小值1
         */
    }



    /**
     * 方法一：
     * 假设当前数据为newNum，先压入stackData，然后判断stackMin是否为空
     * 1. 为空， 压入stackmin
     * 2. 不为空，判断newnum与stackMin栈顶的元素哪个更小
     * 3. 如果newNum更小或者两者相等，则newNum也压入stackMin
     * 4. 如果stackMin中栈顶元素更小，则stackMin不压入任何元素
     *
     */
    public static void push1(int newNum){
        if(stackMin.empty()){
            stackMin.push(newNum);
        }else if(newNum < stackMin.peek()){
            stackMin.push(newNum);
        }
        stackData.push(newNum);
    }

    /**
     * 如果是最小值，就出栈
     */
    public static int pop1(){
        if(stackMin.isEmpty()){
            throw new RuntimeException("empty stack");
        }

        int value = stackData.pop();
        if(value <= getMin()){
            stackMin.pop();
        }
        return value;
    }

    public static int getMin(){
        if(stackMin.empty()){
            throw  new RuntimeException("stack is empty");
        }
        return stackMin.peek();
    }

}
